package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/10 11:46
 *
 整数中1出现的次数
 13(1,10,11,12,13)    6次
 1暴力枚举nlog10 n


 2数学 log10 n
 以算百(某)位进行分析，100-199百位有100个1，t1表示有多少个100，n/1000*100
 t2表示多出来的百位，分为3中情况，无百位，100多，超过200
 可得公式个数=t1+t2
 */

public class Main18 {
    public int NumberOf1Between1AndN_Solution(int n) {
        int ans=0;
        for(int i=1;i<=n;++i){
            int t=i;
            while(t!=0){
                int bit=t%10;
                if(bit==1)ans++;
                t/=10;
            }
        }
        return ans;
    }


    public int NumberOf1Between1AndN_Solution2(int n) {
        int t=1;
        int ans=0;
        while (t<=n){
            int p=t;
            int t1=(n/(p*10))*p;
            int t2=Math.min(Math.max(n%(p*10)-p+1,0),p);
            //System.out.println("p:"+p+"--t1:"+t1+"--t2:"+t2);

            ans+=t1+t2;
            t*=10;
        }
        return ans;
    }
    public static void main(String[] args) {
        System.out.println(new Main18().NumberOf1Between1AndN_Solution2(13));
    }
}
